package com.mlh.greed;

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;

/**
 * @author 缪林辉
 * @date 2024/4/12 11:25
 * @DESCRIPTION
 */
// 假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。
// 每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
// 请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，
// 其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

// 输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
// 输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
// 解释：
// 编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
// 编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
// 编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
// 编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
// 编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
// 编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
// 因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

public class 根据身高重建队列 {
    //本题自己写出，解法描述参考代码随想录

    //贪心策略
    //按照身高排序之后，优先按身高高的people的k来插入，后序插入节点由于都比先插入的节点矮，根本不会影响前面已经插入的节点，最终按照k的规则完成了队列。
    // 所以在按照身高从大到小排序后：
    // 局部最优：优先按身高高的people的k来插入。插入操作过后的people满足队列属性
    // 全局最优：最后都做完插入操作，整个队列满足题目队列属性
    public int[][] method1(int[][] people) {
        //重写Comparator方法，满足本题比较的需求
        Arrays.sort(people,new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0]>o2[0]){
                    return 1;
                }else if(o1[0]==o2[0]&&o1[1]<o2[1]){
                    return 1;
                }else{
                    return -1;
                }
            }
        });
        //利用链表，方便数据的插入
        LinkedList<int[]>temp=new LinkedList<>();
        temp.add(people[people.length-1]);
        //由于我这里身高是从小到大排序的，因此采用逆序遍历的方式
        for (int i = people.length-2; i >=0 ; i--) {
            temp.add(people[i][1],people[i]);
        }
        //将链表转成二维数组
        int[][] res = temp.toArray(new int[0][]);
        return res;
    }

    // public static void main(String[] args) {
    //     int[][]people={{7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2}};
    //     Arrays.sort(people,new Comparator<int[]>(){
    //         @Override
    //         public int compare(int[] o1, int[] o2) {
    //             if(o1[0]>o2[0]){
    //                 return 1;
    //             }else if(o1[0]==o2[0]&&o1[1]<o2[1]){
    //                 return 1;
    //             }else{
    //                 return -1;
    //             }
    //         }
    //     });
    //     System.out.println( Arrays.deepToString(people));

        // LinkedList<int[]> linkedList = new LinkedList<>();
        // linkedList.add(new int[]{1, 2});
        // linkedList.add(new int[]{3, 4});
        // linkedList.add(new int[]{5, 6});
        //
        // // 将LinkedList<int[]>转换为int[][]
        // int[][] intArray2D = linkedList.toArray(new int[0][]);
        //
        // // 打印转换后的二维数组
        // for (int i = 0; i < intArray2D.length; i++) {
        //     for (int j = 0; j < intArray2D[i].length; j++) {
        //         System.out.print(intArray2D[i][j] + " ");
        //     }
        //     System.out.println();
        // }
    // }
}
